# -*- coding: utf-8 -*-
# @File    : test_189.py
# @Date    :  2025-07-25 17:13
# @Author  : zoey1
from typing import List


class Solution:
    """
    面试经典150题-[数组/字符串]-189. 轮转数组
    给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
    """

    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # 没看答案前，自己的实现
        # 判定结果，这个方法时效性不好，很短的list才能实现，对于超大list的需求，会跑很久
        while k > 0:
            origin_value = nums[0]
            for i in range(1, nums.__len__()):
                temp = nums[i]
                nums[i] = origin_value
                origin_value = temp
            nums[0] = origin_value
            k -= 1

    def rotate_20250726(self, nums: List[int], k: int) -> None:
        """
        根据高赞的解题思路的实现
        思路如下：
        首先对整个数组实行翻转，这样子原数组中需要翻转的子数组，就会跑到数组最前面。
        这时候，从 k 处分隔数组，左右两数组，各自进行翻转即可。
        """

        # 翻转方式
        def rotate_all(l):
            half_i = int(l.__len__() / 2)
            l_len = l.__len__()
            for i in range(half_i):
                temp = l[i]
                l[i] = l[l_len - i - 1]
                l[l_len - i - 1] = temp

        k = k % nums.__len__()  # 存在K> list长度的情况，这种取模一下，取模运算，模之后是余数，比如7%3=1
        # 第一步，翻转list
        rotate_all(nums)
        # 第二步，分割左右待处理的list
        nums_before = nums[:k]
        nums_rear = nums[k:]
        # 第三步，前后list，各自翻转
        rotate_all(nums_before)
        rotate_all(nums_rear)
        nums[:] = nums_before + nums_rear  # 切片赋值，替换整个list的内容

    def rotate_review_20250729(self, nums: List[int], k: int) -> None:
        """
        解题思路：
        1、数据倒序，用二分法，两头调换位置
        2、用K，作为分界线，左右两个子数组，再倒序一下
        注意：
        1、数组的引用
        2、注意K可能大于数组长度，需要做取模运算
        """

        def rotate_all(i, j):
            while i < j:
                temp = nums[i]
                nums[i] = nums[j]
                nums[j] = temp
                i += 1
                j -= 1

        rotate_all(0, len(nums) - 1)

        k = k % len(nums)  # ！！！！注意要做取模运算
        rotate_all(0, k - 1)  # ！！！！注意这里要K-1
        rotate_all(k, len(nums) - 1)


if __name__ == '__main__':
    s = Solution()
    nums = [1, 2, 3, 4, 5, 6, 7]
    nums_2 = nums[:]
    k = 3
    # s.rotate(nums, k)
    # s.rotate_20250726(nums, k)
    s.rotate_review_20250729(nums, k)
    print(nums)
